1. Field of the Invention
The invention relates to a method for distributing load over multiple shared resources in a communication network and more particularly in a network having IP (Internet Protocol) packet-supporting capabilities. It also relates to a communication network applying such a method.
2. Brief Description of the Related Art
As known, the use of a method for distributing load over multiple shared resources is typically foreseen at two levels in a communication network, firstly for distributing the load over different paths in the network itself and secondly for distributing the load among links forming a trunk between two network nodes.
The bandwidth of a single transmission link in a network, as foreseen above, does not always suffice to carry all the traffic between a source node and a destination node and a distribution of the traffic load over different paths and/or links from the source to the destination nodes is then usually organized.
On the one hand, trunking is a known solution by means of which a traffic load transmitted between two nodes is divided between several transmission links associated according to selected distribution rules. The links behave as a single physical connection, with a same logical destination address, when they are associated and form a trunk between source and destination nodes. The IP traffic load forwarded from the source node to the destination node is balanced at a central level or at the level of the source by means of a load traffic processing function. Use for distribution purposes of a hashing method is a known solution.
On the second hand, multipath-balancing functions are known for spreading traffic streams of packets in a network according to their respective destinations. Typical applications of such balancing functions are for instance to support an equal cost multipath algorithm (ECMP) for traffic load spreading to underutilized links in a network having IP packet-supporting capabilities and/or to IP trunk groups which spread traffic load across multiple inter-node links.
A known multipath balancing function maintains packet order on a microflow level, being considered that a microflow represents a set of packets with common source IP address, destination IP address, IP protocol, source and destination ports, these ports being for instance TCP (transmission control protocol) ports. Such an order upkeep is important as it avoids packet reordering at their destination. Maintaining order for a set of packets with common source IP address (SRCIP) and destination IP address (DSTIP) suffices to maintain order on the corresponding microflow. Packet sets having respectively same SRCIP and same DSTIP corresponds to a determined flow and each packet of such a determined flow includes a same flow identifying key corresponding to a determined sequence of bits.
As known, the function of the equal cost multipath algorithm ECMP is to classify each packet into one of multiple paths, with all the packets of a same flow classified on a same path.
A known solution for performing a packet classification is based on a hashing function by means of which an identifying key which is a “N” bit number is reduced to an “M” bit number which is used as a path identifier, M being smaller than N with for instance N=64, M=3. Such a function is usually implanted at the level of a processing function and for instance in network processors at the level of the network ingress nodes for balancing source to destination traffic between several links, it is based on the source/destination addressing.
One simple hashing function is based on the extraction of the three most significant bits of the SRCIP address for obtaining a path identifier. But the results are identical for a large percentage of packets and induce unequal spreading across the available multiple paths, It is supposed here that an adequate level of granularity in the spreading function is obtained at the level of a backbone network having IP packet-supporting capabilities.
To avoid the above-indicated drawback and to exploit any difference in their respective keys between two flows, it is appropriate of considering all the bits in a key. The most common prior art solution apply an M-bit cyclic redundancy check (CRC) function to the key for obtaining a M-bit number, i.e. a path identifier, and the space covered by the M-bit output of the CRC function is divided into subspaces, with each subspace corresponding to one of the possible paths. When the output of the hashing function is a number falling in one of the subspaces, the corresponding packet is forwarded to the corresponding path, such for instance a “L” path for a subspace “L”.
However, hashing functions do not work as efficiently as planned due to the fact that the input traffic load is not precisely predictable. For instance, if, in a network, some destination resources are more often addressed than others in a given traffic environment, there is a systematic and unbalanced distribution of traffic load over the destination resources that are shared.
This is illustrated on FIG. 1, for an element of a communication network having IP packet-supporting capabilities in which an ECMP load balancing is performed at the two outputs of four nodes 1, 2, 3, 4 of the tree structured part of the network element. These nodes are supposed to be cascaded through point-to-point L1 paths with a first output of node 1 linked to an input node 2, a first output of node 2 linked to an input of node 3 and a first output node 3 to an input of node 4. It is also supposed that the second output of node 1 is linked to an input of a node 5, the second output of node 2 to an input of node 6 and the second input of node 3 to an input of node 7. Being assumed that nodes 1 to 4 are provided with a same hashing function, all the flows forwarded from source node 1 to node 2 by means of a path L1 are transmitted from node 2 to node 3 by means of a second path L1 and from node 3 to node 4 by a third path L1. There will be no flow forwarded to node 6 from node 2 and from node 3 to node 7 by means of their respective path L2 and an unbalanced distribution of traffic load is systematically obtained.
To avoid such drawbacks, feedback loops are added to load balancing mechanisms to improve the use of shared resources, but they are complex to implement in a network with multiple distributed input network processors and they require remote load measurement means, feedback channels and internal traffic rearrangement functions to avoid out of sequence events in the traffic.